package lev01_beginnerClass.class06_binarySortFind;

import lev01_beginnerClass.util.HelpUtil;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * problem of localminimin
 * precondition: arr is unordered ans tow adjacent number is not equal
 */
public class L04_FindLocalMininum {
    public static void main(String[] args) {
        for(int i = 0; i< 5000;i++){
            int[] arr = HelpUtil.generateRandomArrRejacentNotEqual(20, 10, 50);
            int localMinimum = findLocalMinimum(arr);
            if(!fortest(arr,localMinimum)){
                System.out.println(Arrays.toString(arr));
                System.out.println(localMinimum);
                System.out.println(fortest(arr,localMinimum));
                break;
            }
        }

    }

    /**
     * method to find localminimum
     * @param arr unordered array with two adjacent number is not equal
     * @return
     */

    public static int findLocalMinimum(int[] arr){
        int len = arr.length;
        //give priority to boundary condition
        if(arr == null|| arr.length == 0){
            return  -1;
        }
        if(arr.length == 1){
            return 0;
        }
        if(arr.length == 2){
            return arr[0] < arr[1]? 0:1;
        }
        if(arr[0] < arr[1]){
            return 0;
        }
        if(arr[len-1] < arr[len-2]){
            return len-1;
        }
        int left = 0;int right = len -1;
        //localminimum must exists from left to right
        //why right - left > 1 not left <= right ensurind three number can be find from left to right
        while (right - left > 1){
            int mid = left + ((right - left)>>1);
            if(arr[mid] < arr[mid-1] && arr[mid] < arr[mid+1]){
                return mid;
            }else {
                if(arr[mid] > arr[mid-1]){
                    right = mid -1;
                }else {
                    left = mid +1;
                }
            }
        }
        //localminimum must exists from left to right
        //only two number can be finded forom left to right
        return arr[left] < arr[right] ? left:right;
    }


    /**
     * method for test
     * @param arr
     * @param minIndex  localminumum
     * @return
     */
    public static boolean fortest(int[] arr,int minIndex){
        if(arr == null || arr.length == 0){
            return minIndex == -1;
        }
        int left = minIndex-1;
        int right = minIndex+1;

        //jude left number bigger?
        boolean leftBigger = left >=0 ? arr[minIndex] < arr[left]:true;
        //judge right number bigger
        boolean rightBigger = right < arr.length ? arr[minIndex] < arr[right]:true;

        return  leftBigger && rightBigger;

    }
}
